package com.shexianyu.simple;

/**
 * 53. 最大子序和
 */
public class MaxSubArray {

    //-4, 4, -2, 1, 5, 6, -5, 2
    public int maxSubArray(int[] nums) {
        int pre = 0, maxAns = nums[0];
        for (int x : nums) {
            pre = Math.max(pre + x, x);
            maxAns = Math.max(maxAns, pre);
        }
        return maxAns;
    }

    public int maxSubArray1(int[] nums) {
        int sum = 0;
        int max = nums[0];
        for (int num : nums) {
            sum = Math.max(sum + num, num);
            max = Math.max(sum, max);
        }
        return max;
    }
}
